package Studing;

/**
 * @ClassName TrieeTree
 * @Description: TODO
 * @Author hl
 * @Date 2020/5/30
 * @Version V1.0
 **/
public class TrieeTree {
    class Node{
        Node []children=new Node[26];
        boolean isLeaf;
    }
    Node root=new Node();

    public TrieeTree() {
    }

    public void insert(String word) {
        insert(word,root);

    }

    public void insert(String word,Node node) {
        if(node==null){
            return;
        }
        if(word.length()==0){
            node.isLeaf=true;
            return;
        }
        int index=indexFor(word.charAt(0));
        if(node.children[index]==null){
            node.children[index]=new Node();
        }
        insert(word.substring(1),node.children[index]);
    }

    public boolean search(String word) {
       return search(word,root);
    }
    public boolean search(String word,Node node) {
        if(node==null){
            return  false;
        }
        if(word.length()==0){
            //这里还要判断node节点是不是叶子节点
            return node.isLeaf;
        }
        int index=indexFor(word.charAt(0));
        return search(word.substring(1),node.children[index]);
    }

    public boolean startsWith(String prefix) {
        return  startsWith(prefix,root);
    }

    public boolean startsWith(String prefix,Node node) {
        if(node==null){
            return  false;
        }
        if(prefix.length()==0){
            return true;
        }
        int index=indexFor(prefix.charAt(0));
        return startsWith(prefix.substring(1),node.children[index]);
    }


    private int indexFor(char character) {
        return character-'a';
    }

}
